Activity Selection এবং Job Scheduling Problem গাইড ও নোট

Activity Selection Problem এবং Job Scheduling Problem দুটি ক্লাসিক গ্রীড ভিত্তিক অ্যালগরিদম সমস্যা, যা গ্রীড বা সময়ের ব্যবস্থাপনার ক্ষেত্রে কার্যকরী। এই সমস্যাগুলি সাধারণত সর্বাধিক কার্যকরী সিস্টেম ডিজাইন, রিসোর্স অ্যালোকেশন এবং টাস্ক সিডিউলিং এর জন্য ব্যবহৃত হয়।

এই টিউটোরিয়ালে, আমরা Activity Selection Problem এবং Job Scheduling Problem এর সমাধান Greedy Algorithm ব্যবহার করে Java তে ব্যাখ্যা করব।

1. Activity Selection Problem

Activity Selection Problem হল এমন একটি সমস্যা যেখানে একাধিক ক্রিয়াকলাপ (activities) দেওয়া থাকে, এবং প্রতিটি ক্রিয়াকলাপের একটি শুরু এবং শেষ সময় (start and finish time) থাকে। আমাদের লক্ষ্য হল এমন অনেক বেশি ক্রিয়াকলাপ নির্বাচন করা, যেগুলি একে অপরের সাথে ওভারল্যাপ না করে (মানে তাদের সময়সীমা একে অপরের সাথে মিলে না)।

এই সমস্যা Greedy Approach ব্যবহার করে সমাধান করা যায়।

Steps:

1. প্রথমে ক্রিয়াকলাপগুলো তাদের শেষ সময় অনুযায়ী সাজান।
2. তারপর প্রথম ক্রিয়াকলাপটি নির্বাচন করুন এবং পরবর্তী ক্রিয়াকলাপটি নির্বাচিত করুন যদি তার শুরু সময় পূর্ববর্তী ক্রিয়াকলাপটির শেষ সময়ের পর হয়।

উদাহরণ: Activity Selection Problem

import java.util.*;

class Activity {
    int start, finish;

    public Activity(int start, int finish) {
        this.start = start;
        this.finish = finish;
    }
}

public class ActivitySelection {
    public static void activitySelection(Activity[] activities) {
        // Sort the activities based on their finish times
        Arrays.sort(activities, Comparator.comparingInt(a -> a.finish));

        // The first activity is always selected
        int n = activities.length;
        System.out.println("Selected activities:");
        System.out.println("Start: " + activities[0].start + ", Finish: " + activities[0].finish);

        int lastFinishTime = activities[0].finish;

        // Select the rest of the activities
        for (int i = 1; i < n; i++) {
            if (activities[i].start >= lastFinishTime) {
                System.out.println("Start: " + activities[i].start + ", Finish: " + activities[i].finish);
                lastFinishTime = activities[i].finish;
            }
        }
    }

    public static void main(String[] args) {
        Activity[] activities = {
            new Activity(1, 2),
            new Activity(3, 4),
            new Activity(0, 6),
            new Activity(5, 7),
            new Activity(8, 9),
            new Activity(5, 9)
        };

        activitySelection(activities);
    }
}

ব্যাখ্যা:

1. প্রথমে, ক্রিয়াকলাপগুলো finish time অনুযায়ী সাজানো হয়েছে।
2. পরবর্তীতে, সর্বপ্রথম ক্রিয়াকলাপ নির্বাচন করা হয় এবং তারপর অন্য ক্রিয়াকলাপগুলো নির্বাচন করা হয়, যদি তাদের start time পূর্ববর্তী নির্বাচিত ক্রিয়াকলাপের finish time এর পর থাকে।

আউটপুট:

Selected activities:
Start: 1, Finish: 2
Start: 3, Finish: 4
Start: 5, Finish: 7
Start: 8, Finish: 9

2. Job Scheduling Problem

Job Scheduling Problem হল একটি অপ্টিমাইজেশন সমস্যা যেখানে একটি সেট jobs থাকে এবং প্রতিটি job এর একটি deadline এবং profit থাকে। আমাদের লক্ষ্য হল যে কাজগুলো নির্বাচিত করব, যাতে মোট লাভ সর্বাধিক হয়, তবে যেকোনো job এর সম্পাদনের জন্য তার নির্দিষ্ট deadline এর আগে শেষ হতে হবে।

এই সমস্যা সমাধানে Greedy Approach ব্যবহার করা হয়, যেখানে আমরা প্রথমে সব কাজগুলোকে profit অনুযায়ী সাজাই এবং তারপর সেগুলোর জন্য সঠিক সময় নির্ধারণ করি।

Steps:

1. সকল jobs কে profit অনুযায়ী সাজান।
2. প্রতিটি job এর জন্য সঠিক slot নির্বাচন করুন, যদি তা নির্দিষ্ট deadline এর মধ্যে সম্পাদিত হতে পারে।

উদাহরণ: Job Scheduling Problem

import java.util.*;

class Job {
    int id, deadline, profit;

    public Job(int id, int deadline, int profit) {
        this.id = id;
        this.deadline = deadline;
        this.profit = profit;
    }
}

public class JobScheduling {
    public static void jobScheduling(Job[] jobs, int n) {
        // Sort jobs by decreasing profit
        Arrays.sort(jobs, (a, b) -> b.profit - a.profit);

        boolean[] slots = new boolean[n];  // Tracks free slots
        int totalProfit = 0;

        System.out.println("Job schedule:");

        for (int i = 0; i < n; i++) {
            // Find a free slot for this job (starting from the latest possible)
            for (int j = Math.min(n, jobs[i].deadline) - 1; j >= 0; j--) {
                if (!slots[j]) {
                    slots[j] = true;  // Assign job to this slot
                    totalProfit += jobs[i].profit;
                    System.out.println("Job ID: " + jobs[i].id + " - Profit: " + jobs[i].profit);
                    break;
                }
            }
        }

        System.out.println("Total profit: " + totalProfit);
    }

    public static void main(String[] args) {
        Job[] jobs = {
            new Job(1, 4, 20),
            new Job(2, 1, 10),
            new Job(3, 1, 40),
            new Job(4, 1, 30)
        };

        int n = 4;
        jobScheduling(jobs, n);
    }
}

ব্যাখ্যা:

1. প্রথমে, সকল jobs কে profit অনুযায়ী সাজানো হয়।
2. এরপর, প্রতিটি job এর জন্য, তার deadline এর মধ্যে একটি ফ্রি slot খুঁজে বের করা হয় এবং সেই slot তে job টি সম্পন্ন করা হয়।
3. slots অ্যারে একটি ফ্ল্যাগ হিসেবে কাজ করে, যা কোনো slot ব্যবহৃত হয়েছে কি না তা চিহ্নিত করে।

আউটপুট:

Job schedule:
Job ID: 3 - Profit: 40
Job ID: 1 - Profit: 20
Total profit: 60

সারাংশ

Activity Selection এবং Job Scheduling Problem দুটি জনপ্রিয় সমস্যা যা Greedy Algorithm ব্যবহার করে সমাধান করা হয়।

1. Activity Selection সমস্যার সমাধানে, আমরা finish time অনুযায়ী ক্রিয়াকলাপগুলো সাজাই এবং এমন ক্রিয়াকলাপগুলো নির্বাচন করি যা একে অপরের সাথে ওভারল্যাপ না করে।
2. Job Scheduling Problem সমাধানে, আমরা প্রথমে profit অনুযায়ী jobs গুলো সাজাই এবং তাদের জন্য সঠিক slots নির্বাচন করি যাতে total profit সর্বাধিক হয়।

এই সমস্যা সমাধানগুলো Greedy Approach ব্যবহার করে কার্যকরীভাবে করা যায় এবং Java তে তাদের বাস্তবায়ন দ্রুত এবং দক্ষ।